/* 莫队 O(n*sqrt(m))
    离线算法 分块+暴力
* 1.暴力做法
    记录一个 cnt[x] 数组，表示当前区间 x 出现的次数，
    在两个区间转移时，即左右指针分别移动到对应区间的同时更新 cnt[x]，同时更新答案

* 2.分块策略：将所有区间按左端点分块，同时块内的区间右端点排序再暴力求解

* 3.玄学优化
    对于奇数块内部右端点按照从小到大排序，
    对于偶数块内部右端点按照从大到小排序，
    奇数块和偶数块可以互换

    解释:在第一次滚动时，右端点大概率靠右，如果直接右端点再回到左侧重新滚到右，会多滚一次
                                        如果从右向左滚动，只滚动两次
*/
// #define DEBUG
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
const int N=1e6+10;

inline int read()
{
	int x=0;char c=getchar();
	while (c<'0'||c>'9') c=getchar();
	while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+c-48,c=getchar();
	return x;
}
inline void write(int x)
{
	if (x>=10) write(x/10);
	putchar(x%10+48);
}//快读快输

struct node
{
    int id, l, r;

} query[N];
int n, m, pearl[N], len, cnt[N], res[N];

inline int get(int x)
{
    return x/len;
}

inline void add(int x, int &res)
{
    if(!cnt[x]) res++;
    cnt[x]++;
}

inline void del(int x, int &res)
{
    cnt[x]--;
    if(!cnt[x]) res--;
}

signed main()
{
    #ifdef DEBUG
        freopen("./in.txt","r",stdin);
        freopen("./out.txt","w",stdout);
    #endif

    n=read();// scanf("%d", &n);
    for(int i=1; i<=n; i++) pearl[i]=read();//scanf("%d", &pearl[i]);
    m=read();//scanf("%d", &m);
    len=max(1, (int)sqrt((double(n*n)/m)));

    for(int i=1; i<=m; i++) query[i].l=read(), query[i].r=read(), query[i].id=i;//scanf("%d %d", &query[i].l, &query[i].r), query[i].id=i;
    
    sort(query+1, query+1+m, [](auto &q1, auto &q2){
        int i=get(q1.l), j=get(q2.l);
        if(i!=j) return i<j; //块内排序
        else if(i&1) return q1.r<q2.r; //玄学优化
        return q1.r>q2.r;
    });

    for(int qid=1, i=1, j=0, ans=0; qid<=m; qid++) //[i, j]当前的区间
    {
        int l=query[qid].l, r=query[qid].r;
        // printf("%d %d %d\n", id, l, r);
        while(j<r) add(pearl[++j], ans); //右指针移动到当前范围，加入节点
        while(j>r) del(pearl[j--], ans); //删除多余节点
        while(i<l) del(pearl[i++], ans); //做指针移动到当前范围，删除节点
        while(i>l) add(pearl[--i], ans); //加入节点
        res[query[qid].id]=ans;
    }
    for(int i=1; i<=m; i++)
        write(res[i]), puts("");
    return 0;
}   